package pers.qianyu.month_202101.date_20210103;

import pers.qianyu.util.model.*;

/**
 * 86. 分隔链表
 * https://leetcode-cn.com/problems/partition-list/
 *
 * @author mizzle rain
 * @date 2021-01-03 20:37
 */
public class Partition {
    public ListNode partition(ListNode head, int x) {
        ListNode large = new ListNode(), small = new ListNode(),
                p = head, p1 = small, p2 = large;
        while (p != null) {
            if (p.val < x) {
                p1.next = p;
                p1 = p1.next;
            } else {
                p2.next = p;
                p2 = p2.next;
            }
            p = p.next;
        }
        p2.next = null;
        p1.next = large.next;
        return small.next;
    }
}
